首页 > 试题广场 >

小招喵跑步

[编程题]小招喵跑步

热度指数：10181 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小招喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3种走法，分别是：
1.数轴上向前走一步，即n=n+1
2.数轴上向后走一步,即n=n-1
3.数轴上使劲跳跃到当前点的两倍，即n=2*n
现在小招喵在原点，即n=0，它想去点x处，快帮小招喵算算最快的走法需要多少步？

输入描述:

小招喵想去的位置x

输出描述:

小招喵最少需要的步数

示例1

输入

输出

算法知识视频讲解

Python 3

kkkr

class Solution:
#     最少需要考虑两倍走法
    def minSteps(self, x: int) -> int:
        if x == 0&nbs***bsp;x == 1:
            return x
        
        if x < 0:
            x = (-1) * x
        
        dp = [x] * (x + 1)
        dp[0] = 0
        dp [1] = 1
        
        for i in range(2, x + 1):
            if i % 2 == 0:
                dp[i] = dp[i // 2] + 1   # 就算整除也会变成浮点数
            else:
                dp[i] = min(dp[(i + 1) // 2] + 2, dp[(i - 1) // 2] + 2)
                
        return dp[-1]
    
if __name__ == '__main__':
    x = int(input())
    my_solution = Solution()
    result = my_solution.minSteps(x)
    print(result)

发表于 2022-08-24 19:59:50 回复(0)